home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr46 / strx221.zip / MATCH.CPP < prev    next >
C/C++ Source or Header  |  1993-03-15  |  15KB  |  515 lines
  1. /*
  2.  *
  3.  * Author:    Allen I. Holub 
  4.  *
  5.  * (c) C Gazette. May be used freely as long as author and publication are
  6.  * acknowledged 
  7.  *
  8.  * Roy S. Woll                (Revision 2.0)
  9.  * 1032 Summerplace Dr.
  10.  * San Jose, CA 95122
  11.  *
  12.  * ---------------------------------------------------------------------- 
  13.  *
  14.  *
  15.  * Revision 2.02  14 Mar 1993 ROY S. WOLL
  16.  *
  17.  *   Fixed octal set definition to include first octel digit
  18.  *
  19.  * Revision 2.0   16 Nov 1992 ROY S. WOLL
  20.  *
  21.  *   Initial revision for match.c -> match.cpp
  22.  *   Compatibility with C++ syntax, and now member functions of regX.h
  23.  *   to avoid polluting the name space.  
  24.  *   Fixed some inconsistencies. Regular expression compiled pattern should 
  25.  *   now grow as needed.  Case insensitive support.
  26.  *   
  27.  * Revision 1     27 Jan 1991 Allen I. Holub
  28.  *
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <ctype.h>
  33. #include <string.h>
  34.  
  35. #include "regximp.h"
  36.  
  37. inline const char * max(const char * x, const char * y)
  38.    {if (x>y) return x; else return y;}
  39.  
  40. /* Metacharacters in the input:         */
  41. #define BOL     '^'     /* start-of-line anchor                 */
  42. #define EOL     '$'     /* end-of-line anchor                   */
  43. #define ANY     '.'     /* matches any character                */
  44. #define CCL     '['     /* start a character class              */
  45. #define CCLEND  ']'     /* end a character class                */
  46. #define NCCL    '^'     /* negates character class if 1st char. */
  47. #define CLOSURE '*'     /* Kleene closure (matches 0 or more)   */
  48. #define PCLOSE  '+'     /* Positive closure (1 or more)         */
  49. #define OPT     '?'     /* Optional closure (0 or 1)            */
  50.  
  51. typedef enum action {      // These are put in the pattern string
  52.                            // to represent metacharacters.
  53.   M_BOL =    (0x80 | '^'), 
  54.   M_EOL =    (0x80 | '$'),
  55.   M_ANY =    (0x80 | '.'),
  56.   M_CCL =    (0x80 | '['),
  57.   M_OPT =    (0x80 | '?'),
  58.   M_CLOSE =  (0x80 | '*'),
  59.   M_PCLOSE = (0x80 | '+')
  60. } action;
  61.  
  62.  
  63.  
  64. typedef unsigned char pattern;   /* pattern strings are unsigned char */
  65.  
  66. #define IS_ACTION(x) ((x)&0x80)  /* true => element of pat. string is an   */
  67.                                 /* action that represents a metacharacter */
  68.  
  69. /*----------------------------------------------------------------------*/
  70. #define MAPSIZE 16  /* need this many bytes for character class bit map */
  71.  
  72. /*
  73.  * Advance a pointer into the pattern template 
  74.  * to the next pattern element, this is a +1 for
  75.  * all pattern elements but M_CCL, where you
  76.  * to skip past both the M_CCL character and the
  77.  * bitmap that follows that character
  78.  */
  79.  
  80. #define ADVANCE(pat) (pat += (*pat == (pattern)M_CCL) ? (MAPSIZE+1) : 1)
  81.  
  82. //
  83. // Bitmap functions. Set bit b in the map and
  84. // test bit b to see if it was set previously.
  85. //
  86. #define SETBIT(b,map) ((map)[((b) & 0x7f) >>3] |= (1<< ((b) & 0x07)) )
  87. #define TSTBIT(b,map) ((map)[((b) & 0x7f) >>3] &  (1<< ((b) & 0x07)) )
  88.  
  89. int regXimp::omatch(const char ** strp, const pattern * pat, 
  90.                      const char * start)
  91. {
  92.   /*
  93.    * Match one pattern element, pointed at by pat, against the character at
  94.    * **strp. Return 0 on a failure, 1 on success. *strp is advanced to skip
  95.    * over the matched character on a successful match. Closure is handled one
  96.    * level up by patcmp(). 
  97.    *
  98.    * "start" points at the character at the left edge of the line. This might
  99.    * not be the same thing as *strp if the search is starting in the middle
  100.    * of the string. An end-of- line anchor matches '\n' or '\0'. 
  101.    */
  102.  
  103.   int advance = -1;        // amount to advance *strp, -1 == error
  104.  
  105.   switch (*pat) {
  106.   case M_BOL:              // First char in string?
  107.     if (*strp == start)    // Only one star here.
  108.       advance = 0;
  109.     break;
  110.  
  111.   case M_ANY:              // . = anything but newline
  112.     if (**strp != '\n') advance = 1;
  113.     break;
  114.  
  115.   case M_EOL:
  116.     if (**strp == '\n' || **strp == '\0')
  117.       advance = 0;
  118.     break;
  119.  
  120.   case M_CCL:
  121.     if (TSTBIT(**strp, pat + 1)) advance = 1;
  122.     break;
  123.  
  124.   default:        /* literal match */
  125.     if (caseSensitive){
  126.       if (**strp == *pat) advance = 1;
  127.     }
  128.     else if (toupper(**strp) == toupper(*pat)) advance = 1;
  129.     break;
  130.   }
  131.  
  132.   if (advance > 0)
  133.     *strp += advance;
  134.  
  135.   return (advance + 1);
  136. }
  137.  
  138. #define ISOCTDIGIT(x) ('0'<=(x) && (x)<='7')
  139.  
  140. static int hex2bin(int c)
  141. {
  142.      /* Convert the hex digit represented by 'c' to an int. 'c'
  143.       * must be one of: 0123456789abcdefABCDEF
  144.       */
  145.      return (isdigit(c) ? (c)-'0': ((toupper(c))-'A')+10)  & 0xf;
  146. }
  147.  
  148. static int oct2bin(int c)
  149. {
  150.      /* Convert the hex digit represented by 'c' to an int. 'c'
  151.       * must be a digit in the range '0'-'7'.
  152.       */
  153.      return ( ((c)-'0')  &  0x7 );
  154. }
  155.  
  156.  
  157.  
  158. /*------------------------------------------------------------*/
  159.  
  160. int     esc(const char **s)
  161. {
  162.      /* Map escape sequences into their equivalent symbols. Return
  163.       * the equivalent ASCII character. *s is advanced past the
  164.       * escape sequence. If no escape sequence is present, the
  165.       * current character is returned and the string is advanced by
  166.       * one. The following are recognized:
  167.       *
  168.       *  \b     backspace
  169.       *  \f     formfeed
  170.       *  \n     newline
  171.       *  \r     carriage return
  172.       *  \s     space
  173.       *  \t     tab
  174.       *  \e     ASCII ESC character ('\033')
  175.       *  \DDD   number formed of 1-3 octal digits
  176.       *  \xDDD  number formed of 1-3 hex digits
  177.       *  \^C    C = any letter. Control code
  178.       */
  179.  
  180.      int rval;
  181.  
  182.      if( **s != '\\' )
  183.           rval = *( (*s)++ );
  184.      else {
  185.           ++(*s);                               // Skip the '\'
  186.           switch( toupper(**s) ) {
  187.             case '\0':  rval = '\\';             break;
  188.             case 'B':   rval = '\b' ;            break;
  189.             case 'F':   rval = '\f' ;            break;
  190.             case 'N':   rval = '\n' ;            break;
  191.             case 'R':   rval = '\r' ;            break;
  192.             case 'S':   rval = ' '  ;            break;
  193.             case 'T':   rval = '\t' ;            break;
  194.             case 'E':   rval = '\033';           break;
  195.  
  196.             case '^':   
  197.               rval = *++(*s) ;
  198.               rval = toupper(rval) - '@' ;
  199.               break;
  200.  
  201.             case 'X':   
  202.               rval = 0;
  203.               ++(*s);
  204.               if( isxdigit(**s) ) {
  205.                    rval  = hex2bin( *(*s)++ );
  206.               }
  207.               if( isxdigit(**s) ) {
  208.                    rval <<= 4;
  209.                    rval  |= hex2bin( *(*s)++ );
  210.               }
  211.               if( isxdigit(**s) ) {
  212.                    rval <<= 4;
  213.                    rval  |= hex2bin( *(*s)++ );
  214.               }
  215.               --(*s);
  216.               break;
  217.  
  218.             default:
  219.               if( !ISOCTDIGIT(**s) )
  220.                    rval = **s;
  221.               else {
  222.                    rval = oct2bin( *(*s)++ );
  223.                    if( ISOCTDIGIT(**s) ) {
  224.                         rval <<= 3;
  225.                         rval  |= oct2bin( *(*s)++ );
  226.                    }
  227.                    if( ISOCTDIGIT(**s) ) {
  228.                         rval <<= 3;
  229.                         rval  |= oct2bin( *(*s)++ );
  230.                    }
  231.                    --(*s);
  232.               }
  233.               break;
  234.           }
  235.           ++(*s);
  236.      }
  237.      return rval;
  238. }
  239.  
  240.  
  241. /*----------------------------------------------------------------------*/
  242. const char * regXimp::doccl(const char * src)
  243. {
  244.   /*
  245.    * Set bits in the map corresponding to characters specified in the src
  246.    * character class.  
  247.    */
  248.  
  249.  
  250.   int                first, last, negative;
  251.  
  252.   ++src;                        // skip past the [
  253.   negative = (*src == NCCL);
  254.   if (negative) ++src;          // check for negative ccl
  255.  
  256.   const char * start = src;     // start of characters in class
  257.  
  258.   int len = compiledPattern.length();
  259.   compiledPattern.pad(len+MAPSIZE, str::right, char(0));
  260.   char * map = (char *)compiledPattern(len);
  261.  
  262.   while (*src && *src != CCLEND) {
  263.     if (*src != '-') {
  264.       first = esc(&src);        // Use temp. to avoid macro
  265.                                 // side effects.
  266.       SETBIT(first, map);  
  267.  
  268.     } else if (src == start) {
  269.       SETBIT('-', map);         // literal dash at start or end
  270.       ++src;
  271.     } else {
  272.       ++src;                    // skip to end-of-sequence char
  273.  
  274.      // Support special characters within [].
  275.       last = esc(&src);   
  276.       if (last < first){
  277.          int temp=first;
  278.          first = last;
  279.          last = temp;
  280.       };
  281.  
  282.       while (++first <= last) SETBIT(first, map);
  283.     }
  284.   }
  285.  
  286.   if (*src == CCLEND) ++src;    // Skip CCLEND
  287.  
  288.   if (negative)
  289.     for (first = MAPSIZE; --first >= 0;)
  290.       *map++ ^= ~0;     /* invert all bits */
  291.  
  292.   return src;
  293. }
  294.  
  295. /*----------------------------------------------------------------------*/
  296. const char * regXimp::patcmp(const char * sstr, const pattern * pat, 
  297.            const char * start)
  298. {
  299.   /*
  300.    * Like strcmp, but compares str against pat. Each element of str is
  301.    * compared with the template until either a mis-match is found or the end
  302.    * of the template is reached. In the former case a 0 is returned; in the
  303.    * latter, a pointer into str (pointing to the last character in the
  304.    * matched pattern) is returned. Strstart points at the first character in
  305.    * the string, which might not be the same thing as line if the search
  306.    * started in the middle of the string. 
  307.    */
  308.  
  309.   const char     *bocl;    // beginning of closure string.
  310.   const char     *end=0;   // return value: end-of-string pointer.
  311.  
  312.   if (!pat) return (NULL); // make sure pattern is valid
  313.  
  314.   while (*pat) {
  315.  
  316.     if (*pat == (pattern)M_OPT) {
  317.       /*
  318.        * Zero or one matches. It doesn't matter if omatch fails---it will
  319.        * advance str past the character on success, though. Always advance
  320.        * the pattern past both the M_OPT and the operand. 
  321.        */
  322.  
  323.       omatch(&sstr, ++pat, start);
  324.  
  325.       ADVANCE(pat);
  326.     } else if (!(*pat == (pattern)M_CLOSE || *pat == (pattern)M_PCLOSE)) {
  327.  
  328.      //
  329.      // Do a simple match. Note that omatch() fails if there's still
  330.      // something in pat but we're at end of string. 
  331.      //
  332.       if (!omatch(&sstr, pat, start)) return NULL;
  333.  
  334.       ADVANCE(pat);
  335.  
  336.     } else {         // Process a Kleene or positive closure
  337.  
  338.       if (*pat++ == (pattern)M_PCLOSE) // one match required
  339.         if (!omatch(&sstr, pat, start)) return NULL;
  340.  
  341.      // Match as many as possible, zero is okay
  342.       bocl = sstr;
  343.       while (*sstr && omatch(&sstr, pat, start));
  344.  
  345.       /*
  346.        * 'str' now points to the character that made made us fail. Try to
  347.        * process the rest of the string. If the character following the
  348.        * closure could have been in the closure (as in the pattern "[a-z]*t")
  349.        * the final 't' will be sucked up in the while loop. So, if the match
  350.        * fails, back up a notch and try to match the rest of the string
  351.        * again, repeating this process recursively until we get back to the
  352.        * beginning of the closure. The recursion goes, at most, one levels
  353.        * deep. 
  354.        */
  355.  
  356.  
  357.       if (*ADVANCE(pat)) {
  358.         do {
  359.           end = patcmp(sstr, pat, start);
  360.           if (end) break;
  361.           sstr--;
  362.  
  363.         } while (bocl <= sstr);
  364.         return end;
  365.       }
  366.  
  367.     break;
  368.     };
  369.  
  370.   }
  371.  
  372.   /*
  373.    * omatch() advances str to point at the next character to be matched. So
  374.    * str points at the character following the last character matched when
  375.    * you reach the end of the template. The exceptions are templates
  376.    * containing only a BOLN or EOLN token. In these cases omatch doesn't
  377.    * advance. Since we must return a pointer to the last matched character,
  378.    * decrement str to make it point at the end of the matched string, making
  379.    * sure that the decrement hasn't gone past the beginning of the string. 
  380.    *
  381.    * Note that $ is a position, not a character, but in the case of a pattern
  382.    * ^$, a pointer to the end of line character is returned. In ^xyz$, a
  383.    * pointer to the z is returned. 
  384.    *
  385.    * The --str is done outside the return statement because max() is a macro
  386.    * with side-effects. 
  387.    */
  388.  
  389.   --sstr;
  390.  
  391.   return (max(start, sstr));
  392. }
  393.  
  394.  
  395. /*----------------------------------------------------------------------*/
  396. int regXimp::makepat(const char * exp)
  397. {
  398.   /*
  399.    * Make a pattern template from the string pointed to by exp. 
  400.    * The pattern template is assembled in str compiledPattern.  
  401.    * Regular expression can contain one or more \n characters.
  402.    *
  403.    * Return 1 if success
  404.    */
  405.  
  406.   error = 1;
  407.  
  408.   if (!*exp) goto exit;
  409.  
  410.   if (*exp == CLOSURE || *exp == PCLOSE || *exp == OPT) goto exit;
  411.  
  412.   int prev, len;
  413.  
  414.   len=0;
  415.  
  416.   while (*exp ) {
  417.  
  418.     switch (*exp) {
  419.     case ANY:
  420.       prev=len++;
  421.       compiledPattern += (pattern)M_ANY;
  422.       ++exp;
  423.       break;
  424.  
  425.     case BOL:
  426.       prev=len++;
  427.       compiledPattern += (!compiledPattern.length()) ? (pattern)M_BOL : *exp;
  428.       ++exp;
  429.       break;
  430.  
  431.     case EOL:
  432.       prev=len++;
  433.       compiledPattern += (!exp[1] || exp[1] == '\n') ? (pattern)M_EOL : *exp;
  434.       ++exp;
  435.       break;
  436.  
  437.     case CCL:
  438.       prev=len++;
  439.       compiledPattern += (pattern)M_CCL;
  440.       exp = doccl(exp);
  441.       len += MAPSIZE;
  442.       break;
  443.  
  444.     case OPT:
  445.     case CLOSURE:
  446.     case PCLOSE:
  447.       switch (compiledPattern[prev]) {
  448.         case M_BOL:
  449.         case M_EOL:
  450.         case M_OPT:
  451.         case M_PCLOSE:
  452.         case M_CLOSE:
  453.           goto exit;
  454.       }
  455.  
  456.       compiledPattern.insert(prev,
  457.               (*exp == OPT) ? (pattern)M_OPT :
  458.               (*exp == PCLOSE) ? (pattern)M_PCLOSE : (pattern)M_CLOSE);
  459.  
  460.       len++;
  461.       ++exp;
  462.       break;
  463.  
  464.     default:
  465.       prev=len++;
  466.       compiledPattern += esc(&exp);
  467.       break;
  468.     }
  469.   }
  470.  
  471.   error = 0;
  472.  
  473.  exit:
  474.   return (!error);
  475. }
  476.  
  477. /*----------------------------------------------------------------------*/
  478. const char * regXimp::matchs(const char * sstr, int p_case)
  479. {
  480.   const char     *endp = NULL;
  481.   const char     *start;
  482.   const unsigned char * pat = (unsigned char *)compiledPattern();
  483.  
  484.   caseSensitive = p_case;
  485.  
  486.   if (!pat) return NULL;
  487.  
  488.   if (*sstr == '\0') {
  489.     if ((*pat == (pattern)M_EOL) || 
  490.         (*pat == (pattern)M_BOL && (!pat[1] || pat[1] == (pattern)M_EOL)))
  491.     {
  492.       endp = sstr;
  493.       endMatch = startMatch = sstr;
  494.     }
  495.   } 
  496.   else {
  497.     start = sstr;    // Do a brute-force substring search,
  498.                      // comparing a pattern against the input string
  499.  
  500.     while (*sstr) {
  501.       endp = patcmp(sstr, pat, start);
  502.  
  503.       if (endp) {
  504.          endMatch = endp;
  505.          startMatch = sstr;
  506.  
  507.          break;
  508.       };
  509.       sstr++;
  510.     }
  511.   }
  512.   return endp;
  513. }
  514.  
  515.